{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Searchable Numbers in an Unsorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: binarySearchableNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #未排序数组中的可被二分搜索的数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个 <strong>类似</strong> <a href=\"https://leetcode.com/explore/learn/card/binary-search/\" target=\"_blank\">二分搜索</a>的方法。 这个方法有两个入参: <code>sequence</code> 是一个整数数组， <code>target</code> 是一个整数。 这个方法可以判断 <code>target</code> 是否存在 <code>sequence</code>中。</p>\n",
    "\n",
    "<p>该方法的伪代码如下：</p>\n",
    "\n",
    "<pre>\n",
    "func(sequence, target)\n",
    "  while sequence is not empty\n",
    "    <strong>randomly</strong> choose an element from sequence as the pivot\n",
    "    if pivot = target, return <strong>true</strong>\n",
    "    else if pivot &lt; target, remove pivot and all elements to its left from the sequence\n",
    "    else, remove pivot and all elements to its right from the sequence\n",
    "  end while\n",
    "  return <strong>false</strong></pre>\n",
    "\n",
    "<p>当 <code>sequence</code> 是排好序时, 这个方法对 <strong>所有</strong> 值都可正常判断。如果&nbsp;<code>sequence</code>&nbsp;不是排好序的, 该方法并不是对所有值都可正常判断, 但对<strong>一些</strong> 值仍可正常判断。</p>\n",
    "\n",
    "<p>给定一个仅包含<strong>不同</strong>数字的数组 <code>nums</code>表示 <code>sequence</code>， nums<strong>是否排序未知</strong>，对于 <strong>所有可能</strong>的选择, 返回通过这个方法<b>保证</b>能找到的值的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [7]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释</strong>: \n",
    "7 保证能被找到.\n",
    "因为数组中只有一个数字, 7 一定会被选中. 因为选中的值等于target, 这个方法会返回 true.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [-1,5,2]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释</strong>: \n",
    "只有 -1 保证能被找到.\n",
    "如果 -1 被选中, 这个方法就会返回 true.\n",
    "如果 5 被选中, 5 和 2 会被移除。 在下一次循环时, 这个序列只有一个元素： -1 ，这个方法就会返回 true.\n",
    "如果 2 被选中, 2 将会被移除。 在下次循环时, 这个序列里将会有 -1 和 5. 无论哪个数字被选中, 这个方法都会找到 -1 且返回 true.\n",
    "\n",
    "5 不能保证被找到。\n",
    "如果 2 被选中, -1, 5 和 2 将会被移除。 这个序列将会被清空且这个方法会返回 false。\n",
    "\n",
    "2 不能保证被找到.\n",
    "如果 5 被选中, 5 和 2 将会被移除。在下次循环时, 这个序列只会有一个元素： -1 且这个方法会返回 false。\n",
    "\n",
    "因为只有-1 是保证能被找到的, 你应该返回 1.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;中所有值都&nbsp;<b>不同</b>.</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提升:</strong>&nbsp;如果&nbsp;<code>nums</code> 存在&nbsp;<strong>重复的值</strong>, 你会如何修改你的算法吗?&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-searchable-numbers-in-an-unsorted-array](https://leetcode.cn/problems/binary-searchable-numbers-in-an-unsorted-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-searchable-numbers-in-an-unsorted-array](https://leetcode.cn/problems/binary-searchable-numbers-in-an-unsorted-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7]', '[-1,5,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def binarySearchableNumbers(self, nums: List[int]) -> int:\n",
    "        max_val = -0x7ffffffff\n",
    "\n",
    "        n = len(nums)\n",
    "        flag = [1] * n\n",
    "        for i in range(n):\n",
    "            if max_val > nums[i]:\n",
    "                flag[i] = 0\n",
    "            max_val = max(max_val, nums[i])\n",
    "\n",
    "        min_val = 0x7ffffffff\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if min_val < nums[i]:\n",
    "                flag[i] = 0\n",
    "            min_val = min(min_val, nums[i])\n",
    "\n",
    "        return sum(flag)\n",
    "        \n",
    "\n",
    "    def binarySearchableNumbers2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = float('-inf'), float('inf')\n",
    "        has = [0] * n\n",
    "        for i in range(n):\n",
    "            j = n-1-i\n",
    "            vi, vj = nums[i], nums[j]\n",
    "            if vi > l:\n",
    "                l = vi\n",
    "                has[i] += 1\n",
    "            if vj < r:\n",
    "                r = vj\n",
    "                has[j] += 1\n",
    "        return sum(i==2 for i in has)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binarySearchableNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = float('-inf'), float('inf')\n",
    "        has = [0] * n\n",
    "        for i in range(n):\n",
    "            j = n-1-i\n",
    "            vi, vj = nums[i], nums[j]\n",
    "            if vi > l:\n",
    "                l = vi\n",
    "                has[i] += 1\n",
    "            if vj < r:\n",
    "                r = vj\n",
    "                has[j] += 1\n",
    "        return sum(i==2 for i in has)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binarySearchableNumbers(self, nums: List[int]) -> int:       \n",
    "        # 左向右遍历，当前值左边有没有比它大的\n",
    "        # 右向左遍历，当前值右边有没有比它小的\n",
    "        # 都没有就+1\n",
    "        n = len(nums)\n",
    "        l = [False] * n\n",
    "        last = nums[0] - 1\n",
    "        for i,num in enumerate(nums):\n",
    "            if num > last:\n",
    "                l[i] = True\n",
    "                last = num\n",
    "                \n",
    "        r = [False] * n\n",
    "        last = nums[-1] + 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = nums[i]\n",
    "            if num < last:\n",
    "                r[i] = True\n",
    "                last = num\n",
    "                \n",
    "        return sum(l[i] and r[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 遍历查询\n",
    "    # 根据题意，需要找到一个下标，他左边的数比他小，右边的数比他大，返回所有这样下标的数量。 分别从左往右和从右往左遍历，分别记录最大值和最小值，如果一个数同时是从左往右的最大值和从右往左的最小值，那么符合题意。\n",
    "    def binarySearchableNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = float('-inf'), float('inf')\n",
    "        has = [0] * n\n",
    "        for i in range(n):\n",
    "            j = n - 1 - i\n",
    "            vi, vj = nums[i], nums[j]\n",
    "            if vi > l:\n",
    "                l = vi\n",
    "                has[i] += 1\n",
    "\n",
    "            if vj < r:\n",
    "                r = vj\n",
    "                has[j] += 1\n",
    "\n",
    "        return sum(i == 2 for i in has)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def binarySearchableNumbers(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        max_from_left = [float('-inf')] * n\n",
    "        min_from_right = [float('inf')] * n\n",
    "\n",
    "        # 计算从左到右每个元素的最大值\n",
    "        max_val = float('-inf')\n",
    "        for i in range(n):\n",
    "            max_val = max(max_val, nums[i])\n",
    "            max_from_left[i] = max_val\n",
    "\n",
    "        # 计算从右到左每个元素的最小值\n",
    "        min_val = float('inf')\n",
    "        for i in range(n-1, -1, -1):\n",
    "            min_val = min(min_val, nums[i])\n",
    "            min_from_right[i] = min_val\n",
    "\n",
    "        # 计算可以被找到的元素数量\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if max_from_left[i] <= nums[i] <= min_from_right[i]:\n",
    "                count += 1\n",
    "\n",
    "        return count\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.binarySearchableNumbers([7]))  # 输出应为 1\n",
    "print(sol.binarySearchableNumbers([-1, 5, 2]))  # 输出应为 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binarySearchableNumbers(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      left = [x for x in nums]\n",
    "      right = [y for y in nums]\n",
    "      cur = nums[0]\n",
    "      for i in range(n):\n",
    "        j = nums[i]\n",
    "        left[i] = cur\n",
    "        cur = max(cur,j)\n",
    "      cur = nums[-1]\n",
    "      for i in range(n-2,-1,-1):\n",
    "        j = nums[i]\n",
    "        right[i] = cur\n",
    "        cur = min(cur,j)\n",
    "      ans = 0\n",
    "      for i,j in enumerate(nums):\n",
    "        if left[i]<=j<=right[i]:\n",
    "          ans += 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def binarySearchableNumbers(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        for i in nums:\n",
    "            if len(st) == 0:\n",
    "                st.append(i)\n",
    "            else:\n",
    "                while st and st[-1] > i:\n",
    "                    st.pop()\n",
    "                st.append(i)\n",
    "        st2 = []\n",
    "        for i in reversed(nums):\n",
    "            if len(st2) == 0:\n",
    "                st2.append(i)\n",
    "            else:\n",
    "                while st2 and st2[-1] < i:\n",
    "                    st2.pop()\n",
    "                st2.append(i)\n",
    "        s1 = set(st)\n",
    "        s2 = set(st2)\n",
    "        return len(s1.intersection(s2))\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
